Skip to main content

18 冒险和预测

结构冒险​

CPU 在同一个时钟周期，同时在运行两条计算机指令的不同阶段，可能会用到同样的硬件电路。

把内存分成两部分，存放指令的程序内存和存放数据的数据内存，分别有一个地址译码器。

对程序指令和数据需要的内存空间没办法根据实际的应用动态分配。解决了资源冲突问题，但失去了灵活性。

在 CPU 内部的高速缓存进行区分，分成指令缓存（Instruction Cache）和数据缓存（Data Cache）两部分。

数据冒险​

先写后读（Read After Write）​

int main() {
    int a = 1;
    int b = 2;
    a = a + 2;
    b = a + 3;
}

先读后写（Write After Read）​

int main() {
  int a = 1;
  int b = 2;
  a = b + a;
  b = a + b;
}

写后再写（Write After Write）​

int main() {
  int a = 1;
  a = 2;
}

流水线停顿解决数据冒险​

流水线停顿（Pipeline Stall），或者叫流水线冒泡（Pipeline Bubbling）。

在指令译码时，拿到对应指令需要访问的寄存器和内存地址。判断出指令是否会触发数据冒险。如果会就让整个流水线停顿一个或者多个周期。

NOP 操作和指令对齐​

不同类型的指令，在流水线的不同阶段进行不同的操作。

有些指令没有对应的流水线阶段，不能跳过对应的阶段直接执行下一阶段，否则会触发结构冒险事件。

操作数前推​

add $t0, $s2,$s1
add $s2, $s1,$t0

操作数前推（Operand Forwarding）：前一条指令的执行结果，直接“转发”给下一条指令的 ALU 作为输入。

旁路（Bypassing）：该技术的硬件。ALU 的计算结果，能够重新回到 ALU 的输入。越过（Bypass）了写入寄存器，再从寄存器读出的过程，节省 2 个时钟周期。

填补空闲的 NOP​

代码生成的指令是顺序的，但如果后面的指令不需要依赖前面指令的执行结果，可以不必等待前面的指令运算完成。

a = b + c
d = a * e
x = y * z

乱序执行（Out-of-Order Execution，OoOE）

CPU 里的线程池​

乱序执行是在指令的执行阶段，引入了一个线程池。

  1. 取指令和指令译码时，顺序进行取指令和指令译码。
  2. 进行指令分发，把指令发到保留站（Reservation Stations）。
  3. 指令不会立刻执行，要等它们所依赖的数据，传递给它们之后才会执行。
  4. 指令交到对应的功能单元（Function Unit，FU） ALU 执行。
  5. 完成后不立刻把结果写回到寄存器，而是存放到重排序缓冲区（Re-Order Buffer，ROB）。
  6. CPU 按照取指令的顺序，对指令的计算结果重新排序。只有排在前面的指令都完成了，才会提交指令，完成整个指令的运算结果。
  7. 计算结果不直接写到内存或者高速缓存，而是先写入存储缓冲区（Store Buffer ），最终才会写入高速缓存和内存。

高速缓存解决了 CPU 和内存之间的性能差异，并充分利用了较深的流水线带来的并发性，充分利用 CPU 的性能。

乱序执行的 Tomasulo 算法

控制冒险（Control Harzard）​

为了确保能取到正确的指令，而不得不进行等待延迟：

jmp 后的那一条指令是否应该顺序加载执行，在流水线里进行取指令的时候没法知道。要等 jmp 指令执行完成，去更新 PC 寄存器之后才能知道，是执行下一条指令，还是跳转到另外一个内存地址，去取别的指令。

缩短分支延迟​

条件跳转指令，都在指令译码（ID）的阶段就能获得，只要是简单的逻辑门电路，不需要一个完整的 ALU：

  • 进行条件比较，根据指令的 opcode，就能确认的条件码寄存器。
  • 进行实际跳转，把要跳转的地址信息写入到 PC 寄存器。

可以在 CPU 里设计对应的旁路，在指令译码阶段，就提供对应的判断比较的电路。

静态分支预测​

让 CPU 条件跳转后固定的执行一个分支的指令。

动态分支预测​

根据之前条件跳转的比较结果来预测。

一级分支预测（One Level Branch Prediction）：用当前分支的比较情况，预测下一次分支的比较情况。

引入状态机用更多的信息进行预测。

循环嵌套的改变影响性能​

public class BranchPrediction {
    public static void main(String args[]) {
        long start = System.currentTimeMillis();
        for (int i = 0; i < 100; i++) {
            for (int j = 0; j <1000; j ++) {
                for (int k = 0; k < 10000; k++) {
                }
            }
        }
        long end = System.currentTimeMillis();
        System.out.println("Time spent is " + (end - start));

        start = System.currentTimeMillis();
        for (int i = 0; i < 10000; i++) {
            for (int j = 0; j <1000; j ++) {
                for (int k = 0; k < 100; k++) {
                }
            }
        }
        end = System.currentTimeMillis();
        System.out.println("Time spent is " + (end - start) + "ms");
    }
}

Time spent in first loop is 5ms
Time spent in second loop is 15ms